/**
 * https://leetcode.cn/submissions/detail/565161998/
 * 2616. 最小化数对的最大差值
 * Medium, 黄伟杰 2024.9.16
 * 二分查找
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
    bool check(int mx, int n, vector<int> &nums, int p)
    {
        int cnt = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (nums[i + 1] - nums[i] <= mx)
            {
                cnt++;
                i++;
            }
        }
        return cnt >= p;
    }

public:
    int minimizeMax(vector<int> &nums, int p)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int l = 0, r = nums[n - 1];
        while (l < r)
        {
            int mid = (r + l) / 2;
            if (check(mid, n, nums, p))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};